Through the 1990s, computer networks have grown exponentially. The Internet and the worldwide web have allowed everyone access to extraordinary amounts of information. They have also allowed people to conduct much of their day-to-day business, such as shopping or research using the Internet. During the 1999 shopping season, several large department and toy stores did more business while their stores were actually closed than when they were opened; this was due to their presence on the Internet. Their Internet web sites allowed their customers to look at the products they carry, search for particular items, read about the items, place orders and view delivery information all after the children were tucked quietly in bed. This came as quite a surprise to a large portion of the industry. Merchants had to increase the size and number of their servers to support all of the traffic from the home users. Several had to install significant amounts of new hardware such as network dispatchers to route requests to their servers to redundant or back-up servers so that the response time to the users did not become unbearable.
This is just one of the many examples of how the Internet is growing and how the access to information over the Internet is impacting society today. Users are becoming accustomed to receiving almost instantaneous response from computer networks and will not tolerate delays. As the number of users of the Internet grows, the number of redundant servers and network dispatchers managing these servers also must increase to maintain the quality of service that the customers demand. Network dispatchers are used to manage requests to a server, and distribute the work among several redundant servers, using a predetermined load-balancing methodology.
A typical network dispatcher system is shown in FIG. 6. When the end user device 601 requests information from a server that has a front-end network dispatcher 603, the network dispatcher receives the request and routes it to one of the redundant back-end servers 605, 607, 609. If the network dispatcher 603 subsequently receives another request from the end user device 601, it will go through its selection process again to maintain the continuous load balancing. This is the function of a network dispatcher as it was designed.
The use of the traditional network dispatcher can become a problem when a user, once routed to a server for a first request, must consistently be routed to that same server for repeat requests due to the collection of information. This is so, in the merchant case, where a user comes into the merchant's web site and begins to place an order. Once the first item is placed into a shopping basket, the items must be remembered so that the user can continue to shop and place a successful order.
More specifically, suppose that a cluster of web servers provide equivalent services, front-ended by a network load balancer. The load balancer's job is to route inbound packets to the least-busy server, based on decision-making mechanisms that are beyond the scope of this discussion. A simplified version of this is shown in FIG. 1 where a cellular phone 101 is accessing information on redundant servers 109 using a wireless link 115 to a cellular tower 105, then a land link 117 to a dispatcher 107, then to the information servers 109, while a notebook computer 103 is also accessing information on the same servers 109. The problem becomes how to load balance given that a client, such as the cellular phone 101, must return to a particular server in the cluster 109 for all the flows comprising a session or unit of work. This will be referred to as the “sticky routing” problem.
In the present document, a “session” is defined as a series of related transactions to perform a unit of work. A session generally utilizes HTTP (hyper-text transport protocol) or HTTPS (secure hyper-text transport protocol) flows, consisting of one or more TCP/IP (transmission control protocol/Internet protocol) connections. A simple electronic commerce transaction typically consists of a sequence of related actions such as browsing an online catalog, selecting one or more items of merchandise, placing the order, providing payment and shipping information, and finally confirming or canceling the entire transaction. Information about the state of the session may span multiple TCP/IP connections, since information such as the client's identity, the item desired, the agreed-upon price, payment information, etc. must persist until the entire transaction is complete.
When a given client has a session with a particular server, state information about that session exists only at that particular server. In this case, a load balancer needs to apply extra intelligence to route the packets correctly. In particular, it needs to choose the same server repeatedly as the destination for all inbound packets from a given client for a given session or transaction. This client-server relationship will be referred to as “binding”. To load-balance effectively over time, the system must also release the client's affinity for a particular server between sessions or transactions.
Formerly, a source IP address was unique enough to be used as a discriminator for this type of “sticky” routing. With the present technology, the source IP address is no longer useful as a routing token due to the widespread adoption of NAT (Network Address Translation) and SSL (Secure Sockets Layer). Network Address Translation (NAT) has been widely implemented by ISPs (Internet Service Providers) as a means of connecting the large number of home users to the Internet without using a larger number of registered addresses (since the registered addresses are a limited resource, hence expensive), and to protect the privacy of individual subscribers' IP addresses. The specifications for NAT are set out in the IETF's (Internet Engineering Task Force) RFC (Request for Comment) 1631. The NAT implementation places network address translators 503 at the borders of stub domains, as shown in FIG. 5. Each NAT box has a table consisting of pairs of local IP addresses and globally unique addresses. The IP addresses inside the stub domain are not globally unique. They are reused in other domains. The NAT can be installed without changes to the routers 501 or the hosts, thereby making it very attractive to rapidly growing ISPs.
The ISPs also use DHCP (Dynamic Host Configuration Protocol, RFC number xxxx) or PPP (Point-to-Point Protocol, RFC number xxxx) to dynamically assign private addresses to customer equipment, and use transparent proxies (for things such as the world-wide web, news and multi-media information) as a way of minimizing backbone traffic. NAT, DHCP/PPP and transparent proxies solved the addressing problems in expanding always connected home networks, reduced the costs of providers' backbones and helped restrain hackers from taking advantage of open ports to end-user equipment, but these steps resulted in the loss of the unique IP address for the user.
With the advent of NAT and transparent proxies, one can no longer safely assume that a single IP address applies to just one client. In fact, it is a goal of a NAT to conceal the host's true local IP address by substituting some constant IP address for the true IP address. NAT technology is commonly used in a device that connects a multiplicity of mobile clients to the Internet, such as a Wireless Access Protocol (WAP) gateway, and also appears in home networking devices such as a LAN router or smart hub or in modems for the home (3Comm's ISDN LAN modem is an example of a small router for the home incorporating NAT function). NAT devices and transparent proxies are also deployed by ISPs offering “always on” types of services such as those based on cable modem or Asymmetric Digital Subscriber Loop (ADSL) technology as well as in traditional dial-up “Point of Presence” (POPs).
The SSL-ID (Secure Sockets Layer Identifier) has also been tried as a solution to the sticky routing problem and failed. Connections using the SSL or TLS are encrypted. Once an SSL connection is established between a given client and a particular server, the SSL ID (a quasi-unique number) could be examined by the load-balancer and used for sticky routing purposes. Although the SSL standard always permitted either endpoint of the connection to repudiate the key agreement and force a renegotiation of SSL parameters and consequently the assignment of a new SSL-ID, in practice only servers did this, making the approach viable for a while. However, with the recent release of Microsoft Internet Explorer 5.0, this technique is no longer viable. Internet Explorer 5.0 is coded such that either the server or the client may repudiate the key agreement, making it impossible for a load-balancer to correlate the former SSL connection with the current one.
The next solution attempted for both of these problems employed “cookies”. A cookie is a data object transported in variable-length fields within the HTTP header that is normally stored on the client, either for the duration of the session or permanently. A cookie stores certain data that the server application wants to remember about a particular client. This could include client identification, session parameters, user preferences, session state, or almost anything else an application writer can think of. Although a load-balancer with content-based routing could look into the HTTP header and route based on data contained in cookies, this initially promising solution also turned out to have a disastrous flaw. Certain clients are incapable of storing cookies.
These certain clients include webphone clients that access the Internet through a WAP gateway using the Wireless Session Protocol (WSP). WSP does not include cookies. Even if WSP supported cookies, the webphone clients are not capable of storing cookies due to their extremely limited memory. While it is possible for a wireless gateway product to store cookies on behalf of the wireless client (the IBM eNetwork Wireless Gateway does this; the Nokia WAP gateway does not), such functions in the gateway cannot be assumed, as is demonstrated above. In addition, with increasing privacy concerns about the use of cookies by unscrupulous advertisers to track an Internet user's surfing habits, many users are choosing to disable cookies altogether, or turn on cookie prompting, accepting cookies selectively, if at all. So the capability of storing persistent session information in cookies cannot be presumed.